package leetcode_400;

/**
 *@author 周杨
 *UTF8Validation_393 检查一个int数组里编码是否为合法的utf-8编码
 *describe:用掩码 AC 99%
 *2018年7月13日 下午7:59:52
 */
public class UTF8Validation_393 {

	
	public static void main(String[] args) {
		UTF8Validation_393 test=new UTF8Validation_393();
		int []res=test.getByte(240);
		for(int i:res)
			System.out.print(i+" ");
		System.out.println(Integer.toBinaryString(240));
		System.out.println(Integer.toBinaryString(162));
		System.out.println(Integer.toBinaryString(138));
		System.out.println(Integer.toBinaryString(147));
	}
	
	public boolean validUtf8(int[] data) {
		if(data.length>=5)
			return false;
        int judge=data[0];
        int ju[]=getByte(judge);
        int count=0;
        while(count<8&&ju[count]!=0)
        	++count;//判断是几位有效码
        if(count==0)
            return true;
        if(count==1)
        	return false;
        if(count>4)
        	return false;
        if(data.length<count)
        	return false;
        for(int i=1;i<count;++i) {//否则是 2 3 4 
        	int now[]=getByte(data[i]);
        	if(!(now[0]==1&&now[1]==0))
        		return false;
        }
        return true;
  }
	
	
	private int[] getByte(int data) {
		int[] res=new int[8];
		for(int i=0;i<8;++i) {
			res[7-i]=(data>>i)&1;
		}
		return res;
	}
		
	
	
	 /**
	 * describe:AC算法 99%
	 * 2018年7月13日 下午8:01:26
	 */
	public boolean validUtf81(int[] data) {
	       /* 1. check how many '1's = ones
	         * 2. check (i + 1, i + ones - 1) for '10'
	         * 3. update i = i + ones
	         * valid ones: 0, 2, 3, 4
	         */
	        int i = 0;
	        while(i < data.length) {
	            // 1. find ones
	            int ones = 0;
	            while(((data[i] >> (7 - ones)) & 1) == 1) {
	                ones++;
	            }
	            // invalid ones 
	            if(ones == 1 || ones > 4) return false;
	            // 2. check 1s
	            i++;
	            while(ones-- > 1) {
	                if(i >= data.length || ((data[i] >> 6) & 3) != 2) return false;
	                // 3. update i
	                i++;
	            }
	        }
	        
	        return true;
	    }
	    
}
